package cn.zj90.algorithm;

/**
 * Created by zj90 on 17/7/25.
 */
public class QuickSort {

    private int partition(int array[], int startIdx, int endIdx) {
        int leftCursor = startIdx;
        int rightCursor = endIdx;
        int pivot = array[startIdx];

        while (leftCursor < rightCursor) {
            while (leftCursor < rightCursor && array[rightCursor] >= pivot) rightCursor--;
            if (leftCursor < rightCursor) array[leftCursor++] = array[rightCursor];

            while (leftCursor < rightCursor && array[leftCursor] <= pivot) leftCursor++;
            if (leftCursor < rightCursor) array[rightCursor--] = array[leftCursor];
        }
        array[leftCursor] = pivot;

        return leftCursor;
    }

    public void sort(int array[], int startIdx, int endIdx) {
        int pivotIdx = partition(array, startIdx, endIdx);
        sort(array, startIdx, pivotIdx - 1);
        sort(array, pivotIdx + 1, endIdx);
    }

}
